FIG. 1 illustrates a prior art arrangement of a transmitter, propagation channel and a receiver having a viterbi equalizer for compensation of time delayed echoes of the signal propagated through the channel.
The demodulation of digitally modulated radio signals received through a channel that results in inter-symbol interference may be achieved by the use of a Viterbi algorithm for Sequential Maximum Likelihood Sequence Estimation (SMLSE), also known as the Viterbi equalizer. The Viterbi equalizer, which is well known in the art, uses a linear and finite impulse response model of the channel to predict the signal sample values that should be received from each possible data pattern that can be contained in the channel impulse response time span. The equalizer compares each prediction with the actual received signal sample values, and accumulates "votes" for or against the possibility of each data pattern being the correct data pattern based upon the accuracy of the match between the predicted signal and the actually received signal. However, not all prediction sequences are valid. For example, predicting that the data sequence is 10010 at one instant and 11001 at the next instant are not compatible. The sequence 10010 can only be followed by the sequence 00100 or 00101 when the sequence 10010 is left shifted through the channel and a new 0 (or 1) is added. Likewise, a new sequence 00100 or 00101 can have only a sequence of 10010 or 00010 as a predecessor. As a result, a set of transition rules constrains how "votes" may sequentially be accumulated for each candidate prediction sequence.
The equalizer typically selected implements a linear, finite-impulse-response ("FIR") model of the channel consisting of a transversal filter, i.e., a tapped delay line having complex multiplication weights which are applied to the tap outputs. The weighted outputs are summed to predict, for each possible data symbol pattern that can be contained within the time span of the channel's impulse response, the signal value that should be received for the next data symbol. The predicted values are compared with the actually received signal values, and "votes" for and against the probability of each data symbol pattern being "correct" (i.e., the pattern transmitted) are accumulated. Each "vote" is based on the accuracy of the match between a predicted sequence of values and the received sequence. The data symbol patterns that can be contained within the time span of the channel's impulse response correspond to the "states" of the system.
The weights applied to the delay line tap outputs are the coefficients, c.sub.1, c.sub.2 2, c.sub.3, . . . , in the equation: EQU S.sub.i :c.sub.1 d.sub.i +c.sub.2 D.sub.i-1 +c.sub.3 D.sub.i-2 +. . .
where S.sub.i is the predicted signal for the sequence of data symbols D.sub.i, D.sub.i-1, D.sub.i-2, . . . The coefficients are usually calculated from a known training pattern. In the case of signalling by binary data symbols (i.e., 1 and 0), the number of predicted signals that must be calculated is 2.sup.n, where n is the impulse response length of the channel in symbol periods. It will be understood that ternary and quaternary data symbols can also be used. In these cases, the number of predicted values would be 3.sup.n or 4.sup.m correspondingly.
The known Viterbi equalizer incorporates the following steps: (1) determining the tap coefficients for a Finite Impulse Response (FIR) model of a channel; (2) for all possible data symbol sequences that can be postulated to be within the impulse response length of the channel model, predicting the signal value that should be received based on the determined tap coefficients; (3) comparing each postulated value with the actually received signal value and calculating the mismatch (usually by squaring the difference between the received and postulated values); (4) for each postulated symbol sequence, adding the calculated mismatch to the cumulative mismatch of predecessor sequences that are consistent with the postulated symbol sequence, also called "the state" (the cumulative mismatch values are called "path metrics"); and (5) choosing the "best" of the possible predecessor sequences that can transition to the new postulated state, i.e., choosing the predecessor sequence which gives the lowest path metric for the new state. Thus, the path metrics can be considered as confidence factors that represent the degrees of correlation between the postulated symbol sequences and the actual received signal.
FIG. 2 illustrates the data structure and flow within a Viterbi equalizer having 16 states, the predicted signal values being assumed to depend on four previous binary symbols (bits) plus one new bit. The channel impulse response length for this example is thus five symbols, i.e. the latest echo can be four symbols delayed compared to the shortest signal path.
Referring to FIG. 2, a Viterbi processing cycle begins by assuming the postulated symbol history of state 0000 to be true, and that a new bit `0` was transmitted. Consequently, using the channel model 40, the signal value that should be observed given the 5-bit symbol history 00000 is predicted. This is compared in comparator 50 with the actual received signal value and a mismatch value produced. The mismatch value is added in adder 51 with the previous cumulative mismatch for the symbol history of state 0000 to produce a new candidate path metric for a new 0000 state.
However, another candidate for the new path metric of new state 0000 can be derived by assuming state 1000 to contain the true history, with a new bit of `0`. This is because both 0000-0 and 1000-0 lead to new state 1-0000 (0-0000) when the oldest (left-most) bit is left shifted out of the 4-bit state number and into the symbol history memory. This candidate is evaluated by applying 10000 to the channel model 40, comparing the prediction so-obtained with the input signal value in comparator 50 and adding the resultant mismatch with the previous cumulative mismatch (path metric) associated with state 1000 in adder 52. The two candidate values from adders 51 and 52 are then compared in a comparator 53, and the lower of the two is selected to become the new path metric of new state 0000. Furthermore, the content of the history memory 55 associated with the selected predecessor state is selected to be the symbol history of the new state 0000. Also, this selected bit history is left-shifted and a 0 or 1 entered in the right-most position according as state 0000 or 1000 gave rise to the selected candidate path metric.
The above procedure is then repeated with the assumption that the new bit is a `1` in order to produce a new state 0001, also with either state 0000 or 1000 as candidate predecessors.
The above procedure is then repeated using every pair of states , which are 8 states apart, to derive all 16 new states, as follows:
0001, 1001 to produce new states 0010 and 0011
0010, 1010 to produce new states 0100 and 0101
0011, 1011 to produce new states 0110 and 0111
0100, 1100 to produce new states 1000 and 1001
0101, 1101 to produce new states 1010 and 1011
0110, 1110 to produce new states 1100 and 1101
0111, 1111 to produce new states 1110 and 1111
At the end of the above processing cycle, one signal sample has been processed and one extra bit has been demodulated and inserted into symbol history memories 55. There is a tendency for the older bits in the history memories to converge to the same value, at which point that bit can be extracted as a final, unambiguous decision and the history memory shortened by 1 bit.
Other methods of truncating history memory growth are known to the art, such as taking the oldest bits from the state having the lowest path metric.
A variation on the implementation of the Viterbi equalizer is to use the channel model in advance to predict the expected signal for all possible symbol sequences, 32 distinct values for the example illustrated in FIG. 2, and to store them in a memory. This can reduce the complexity of the system in terms of the total number of calculations needed, when the channel model and therefore the signal predictions are expected to be constant for a large number of demodulated symbols. On the other hand, if the channel is time varying such that it must be updated constantly, then recalculation of all predictions must be performed for each demodulated symbol with the new channel model, so pre-calculation is not an advantage.
The prior art deals with methods for updating the channel models from the received signal. One prior art method maintains a separate channel model for each Viterbi state. When the best predecessor state is selected to survive, the channel model belonging to the surviving predecessor state is updated and becomes the channel model for the new state. By using this method, the surviving channel models are always derived from the best demodulated data sequences to date.